package com.edu.leetcode.dataStruct;

import java.math.BigDecimal;

/**
 * 给你一个整数 n ，请你找出并返回第 n 个 丑数 。
 * 丑数 就是只包含质因数 2、3 和/或 5 的正整数。
 *（现在写的是一个贼吃时间的程序）
 * @作者 five-five
 * @创建时间 2021/4/11
 */
public class Demo17 {
    public static void main(String[] args) {
        Demo17 demo17 = new Demo17();
        long a = System.currentTimeMillis();
        System.out.println(a);
        int nthUglyNumber = demo17.nthUglyNumber(1324);
        System.out.println(nthUglyNumber);
        long b = System.currentTimeMillis();
        System.out.println(b);
        BigDecimal bigDecimal = new BigDecimal((b-a)/1000);
        System.out.println(bigDecimal);
    }

    /**
     * @param n
     * @return
     */
    public int nthUglyNumber(int n) {
        int count = 0;
        for (int i = 1; true; i++) {
            if (isUgly(i)) {
                //计数器加一
                count++;
            }
            if (count == n) {
                return i;
            }
        }
    }

    /**
     * 看他的乘数是否只有2,3,5.如果有其余的那就不能算是丑数
     *
     * @param n
     * @return
     */
    public boolean isUgly(int n) {
        return n != 0 && help(n);
    }

    /**
     * 递归方法
     *
     * @param n
     * @return
     */
    private boolean help(int n) {
        if (n == 1) {
            return true;
        }
        //开始进行触发
        if (n % 2 == 0) {
            return help(n /= 2);
        }
        if (n % 3 == 0) {
            return help(n /= 3);
        }
        if (n % 5 == 0) {
            return help(n /= 5);
        }
        return false;
    }
}
